\section{Overview of Analysis of the Approximation Ratio}\label{sec:overview}

%\textbf{Intuition:} The possibility of improving the approximation
%factor follows from the fact that our algorithm generalizes previous
%algorithms (i.e., McGregor's and Zelke's algorithm consider a path
%$P$ of length $3$ and $7$ respectively). In particular, it allows
%more opportunity for an edge to be added to the matching as it
%acquires help in sharing the burden of charge from other shadow
%edges. Moreover, considering many edges helps ``balancing out'' the
%charge.
%%
%However, the global improvement means that charge has to be moved
%globally as well: Unlike the previous algorithm where charge carried
%on one edge is moved to its neighboring edges only, this algorithm
%may have to move charge to other faraway edges because the
%neighboring edges are not large enough to carry this charge. This
%brings too much complication to the charging argument.
%%
%This complication is dealt with by series of methods. First, the
%algorithm is constructed to limit changes to be on the part that
%allow charge to be done locally most of the time. This leaves us
%only a few cases that need to move charge globally. Second, we show
%that some structural properties of the graph can be assumed so that the
%complicated cases are easier to handle. This makes it
%possible to deal with a few cases with global charging.

%
In this section, we provide an outline of the proof of our main
theorem. We first formalize some notation. For any weighted graph
$G$ and any $\gamma>1$, let $ALG(G, \gamma)$ be the solution output
by Algorithm~\ref{alg:shadow_algorithm} when $G$ and $\gamma$ are
input and \textit{$G$ is read in the worst-case order}. Let $OPT(G)$
be an optimal solution. When $G$ and $\gamma$ is clear from the
context, we simply write $ALG$ and $OPT$. Let $w(ALG)$ and $w(OPT)$
be the total weight of edges in $ALG$ and $OPT$ respectively. Again,
when it is clear from the context, we abuse the notation and refer
to $w(ALG)$ and $w(OPT)$ as $ALG$ and $OPT$, respectively. We prove
the following theorem.

\begin{theorem}\label{thm:main}
%For any weighted graph $G$ and $\gamma>0$,
%$$\frac{OPT(G)}{ALG(G,\gamma)}\leq \max\{\alpha+\gamma,
%\beta+2\gamma\}+\frac{1}{(\gamma^2(\gamma-1))}$$ where,
%$\alpha=\frac{\gamma^3-1}{\gamma^2(\gamma-1)}$ and
%$\beta=\frac{\alpha+\gamma-1}{\gamma}$.
For any weighted graph $G$ and $\gamma>0$,
$$\frac{w(OPT(G))}{w(ALG(G,\gamma))}\leq \max\{\alpha+\gamma,
\beta+2\gamma\}$$ where,
$\alpha=\frac{\gamma}{\gamma-1}$ and
$\beta=\frac{\alpha+\gamma-1}{\gamma}$.
\end{theorem}

The approximation ratio of 5.24 follows from the theorem using
$\gamma=1.7$.

Our analysis follows a charging scheme, as with all the previous
streaming algorithms for this problem. However, we make some key
simplifying assumptions on the input graph that can be made without
loss of generality. These are described in
Section~\ref{sec:simplify_input_graph}. We now describe the main
idea behind this charging scheme and reserve the case based analysis
for subsequent sections. First, look at each edge in the optimal
solution, denoted by $e^*$, and place a ``charge'' of amount
$w(e^*)$ on some edges. For any $\rho$, to show that the solution is
$\rho$-approximation, it is enough to argue that one can move all
this charge to the edges in the algorithm's solution ($ALG$) in such
at way that each edge $e$ in $ALG$ receives at most $\rho\cdot w(e)$
charge.

We now define variables we need in the charging scheme and
properties of this charging scheme. Recall that $G$ denotes the
input graph with edges arriving from the stream in order $e_1, e_2,
..., e_m$. For any $t\in [0, m]$, let $M_t$ be the matching $M$
stored by the algorithm after the edge $e_t$ is processed. (Note
that $M_0=\emptyset$ and $M_m=ALG$.) For any $t$ and any vertex $v$,
if there is an edge $e$ in $M_t$ incident to $v$ then let
$M_t(v)=e$; otherwise, let $M_t(v)=\emptyset$. For convenience, we
define the weight of an empty set to be zero.

Similar to~\cite{Zelke08}, our charging scheme places charge on
vertices as well as edges. For any $t$ and for any edge $uv\in E$,
we define variables $ch_t(u)$, $ch_t(v)$, and $ch_t(uv)$, to be
variables keeping charge (related to $uv$ at time $t$).
%In addition, for any edge $uv$ define a charge variable $l_t(uv)$. We use
%$l_t(uv)$ to keep some charge separately from $ch_t(uv)$ to simplify the analysis.

To prove the approximation guarantee, we place a total of $OPT(G)$
charge on these variables. As the algorithm progresses we move them
among the variables to maintain an invariant.
% to account for the charging scheme.
Intuitively, we move around charge such that (1)
there is no charge lost, (2) only edges in the matching carry
positive charge, and (3) each edge does not carry too much charge.
We precisely maintain the following invariant.

\begin{invariant}\label{inv:main}\hfill
\begin{enumerate}
%\squishlist
%\item \label{inv:charge_more_than_opt} The total
%charge in $G$ is at least $OPT(G)$. I.e., $\sum_{t=1}^m \sum_{x \in
%V(G)\cup E(G)} ch_t(x) +
%\sum_{t=1}^m \sum_{e \in E(G)} l_t(e)\geq OPT(G).$ %(I.e., the total
%%charge in $G$ is at least $OPT(G)$.)
\item \label{inv:charge_more_than_opt} The total
charge in $G$ is at least $OPT(G)$. I.e., $\sum_{t=1}^m \sum_{x \in
V(G)\cup E(G)} ch_t(x)\geq OPT(G).$ %(I.e., the total
%charge in $G$ is at least $OPT(G)$.)
\item \label{inv:charge_on_matching_only} Only matched edges keep charge.
I.e., for any $t$ and for any $uv\notin M_t$, $ch_t(uv)=0$.
For any $t$ and for any $v\in V(G)$ that is not covered by the
matching $M_t$, $ch_t(v)=0$.
%%
%\comment{ %MAY NEED THIS LATER
%\item \label{inv:unique_time} Each vertex and each ``copy'' of an edge
%cannot keep charge at two different points of time simultaneously.
%I.e.,
%\begin{itemize}
%\item for any $v\in V(G)$ and any $t$, if $ch_{t}(v)>0$
%then $ch_{t'}(v)=0$ for any $t'\neq t$, and
%\item for any $e\in E(G)$ and any $t$, if $ch_{t}(e)>0$
%then $ch_{t'}(e)=0$ for any $t'\neq t$ such that for every $t''$
%between $t$ and $t'$, $e\in M_{t''}$.
%\end{itemize}
%%
%Moreover, for any $v\in V(G)$, if $ch_{t}(v)>0$ then an optimal edge
%that covers $v$ arrives after time $t$ (i.e., there exists
%$e_{t'}\in OPT$ where $t'>t$ and $v\in e_{t'}$). }
%
\item \label{inv:unique_time} Each vertex and edge
cannot keep charge at two different points of time simultaneously.
I.e., for any $x\in V(G)\cup E(G)$ and any $t$, if $ch_{t}(x)>0$
then $ch_{t'}(x)=0$ for any $t'\neq t$.
%\comment{Moreover, for any
%$v\in V(G)$, if $ch_{t}(v)>0$ then an optimal edge that covers $v$
%arrives after (OR BEFORE???) time $t$ (i.e., there exists $e_{t'}\in
%OPT$ where $t'>t$ and $v\in e_{t'}$).}
%
\item \label{inv:charge_limit} Each edge has charge limit (depending on its weight). That
is,
%\begin{enumerate}
%\item
for any $t$ and any $uv\in
M_{t}$, one of the following is true.
%\begin{itemize}
\squishlist
\item $ch_{t}(uv)\leq \alpha w(uv)$ and either $ch_{t'}(u)=0$ for all $t'\leq t$ or $ch_{t'}(v)=0$ for all $t'\leq t$.
\item $ch_{t}(uv)\leq \beta w(uv)$.
\squishend
%\end{itemize}
Moreover, $ch_{t}(u)\leq \gamma w(uv)$ and $ch_{t}(v)\leq \gamma
w(uv)$. Here, $\gamma$, $\alpha$, and $\beta$ are defined as in
theorem~\ref{thm:main}.
%\item \label{inv:charge_on_l} For all $uv\in E(G)$ and $t<m$, $l_t(uv)\leq w(uv)/\gamma^2$.
%For all $uv\in E(G)$, $l_m(uv)=0$. Moreover, if $l_t(uv)>0$ then
%$uv\notin M_{t+1}$.
%\end{enumerate}
\end{enumerate}
%\squishend
\end{invariant}

The goal of this charging scheme is to move charge around so that at
the end, all the charge is on the edges in $ALG$. The following
lemma states precisely the condition when the algorithm terminates.

\begin{lemma}\label{lem:finish_charging_scheme}
After the charging scheme is finished, for all $t<m$ and $uv\in E$,
$ch_t(u)=ch_t(v)=ch_t(uv)=0$.
\end{lemma}

What this says is that all the charge on vertices or edges for time
$t<m$ are moved to charges at time $m$; i.e., there is no charge
``left over'' from previous time steps that we do not account for.
We prove this lemma in section~\ref{sec:proofs}, after we describe
the charging scheme.
%
Now we are ready to prove the main theorem, assuming that we have a
charging scheme that satisfies invariant~\ref{inv:main} and
lemma~\ref{lem:finish_charging_scheme}.


\begin{proof}[Proof of theorem~\ref{thm:main}]
Note that we have the following at the end of the charging scheme.
%
\begin{eqnarray*}
OPT&\leq& \sum_{t=1}^m\sum_{uv\in M_m} ch_t(u)+ch_t(v)+ch_t(uv)
\text{\ \ \ \ (By Invariant~\ref{inv:main}(\ref{inv:charge_more_than_opt}))}\\
&=& \sum_{uv\in M_m} ch_m(u)+ch_m(v)+ch_m(uv)\text{\ \ \ \ (By
Lemma~\ref{lem:finish_charging_scheme})}\\
&\leq & \max\{\alpha+\gamma, \beta+2\gamma\}\sum_{uv\in
M_m}w(uv).\text{\ \ \ \ (By
Invariant~\ref{inv:main}(\ref{inv:charge_limit}))}
\end{eqnarray*}
%\qed
This completes the proof.
%\qed
\end{proof}
%

%COMMENTED BELOW ABOUT LEFT OVERS. TO COMMENT THIS ELSEWHERE IN THIS SECTION TOO!!!!

%Since $M_m=ALG$, it is left to show that
%$$\sum_{t=1}^m \sum_{e\in E(G)} l_t(e) \leq
%ALG/(\gamma^2(\gamma-1)).$$

%We redistribute the charge as follows. Do the following from $t=1$
%until $t=m-1$. For any $uv\in M_t$ with $l_t(uv)>0$, let $u'u$ and
%$v'v$ be two edges that eat $uv$. (Use the similar argument if $uv$
%is eaten by one edge.) Distribute charge $f_t(u)l_t(uv)$ to
%$l_{t'}(u'u)$ and  $f_t(v)l_t(uv)$ to $l_{t''}(u'u)$ where $t'$ and
%$t''$ are the time $u'u$ and $v'v$ are eaten respectively.

%Once we finish the redistribution, all charge will be at $l_m(uv)$
%for $uv\in M_m$ only. How much charge does an edge $uv\in M_m$ get?
%$uv$ receives charge from at most two edges, say $uu'$ and $vv'$
%with total weight $(f_t(u)w(uu')+f_t(v)w(vv'))/\gamma^2\leq
%w(e)/\gamma^3$ for some $t$. Moreover, $uu'$ and $vv'$ may receive
%charge from other edges with total weight $(w(e^1)+w(e^2))/\gamma^3$
%which contributes to $e$ at most $w(e)/\gamma^4$. By this argument,
%the total weight $e$ has eaten is $w(e)(1/\gamma^3+1/\gamma^4+ ...)
%\leq w(e)/(\gamma^2(\gamma-1))$ as claimed.
%\qed
%\end{proof}


\section{Locally Exceeding}
One ingredient in our proof is the following property of the
algorithm which we use repeatedly in the charging scheme. It appears
in a slightly different form and is called ``locally
$\gamma$-exceeding'' in~\cite[Lemma~2]{Zelke08}. It requires a new
proof in our case because we have a global algorithm.

\begin{lemma}\label{lem:charge_eating}
For any $t\in [0, m-1]$, there exists a function $f_t:
V(G)\rightarrow [0, 1]$ such that
%\begin{itemize}
\squishlist
\item $\forall cd\in M_t\setminus M_{t+1}: f_t(c)+f_t(d)\geq 1$
\item $\forall ab\in M_{t+1}\setminus M_t$: $f_t(a)\cdot w(M_t(a))+f_t(b)\cdot
w(M_t(b))\leq w(ab)/\gamma$ \squishend
%\end{itemize}
\end{lemma}
%\begin{proof} This is a direct consequence of the algorithm. WE PUT
%IT HERE FOR COMPLETENESS ???? \end{proof}

For an intuition, let us say that an edge $e\in M_t\setminus
M_{t+1}$ is \textit{eaten} by two edges $e_1$ and $e_2$ in $M_{t+1}$
if $e_1$ and $e_2$ share the end vertices with $e$. Suppose $e_1$
and $e_2$ shares a vertex $u$ and $v$ with $e$ respectively. Imagine
that $e_1$ ($e_2$) eats $f_t(u)$ ($f_t(v)$) fraction of $e$. The
first statement in the above lemma says that $e$ is fully eaten
while the second statement says that $e_1$ who might have eaten $e$
and another edge $e'$ will eat at most $1/\gamma$ of its weight in
total.
%This intuition will be useful in the following proof.

\begin{proof} [Proof of Lemma~\ref{lem:charge_eating}]
Our algorithm considers long alternating paths between matching
edges and shadow edges. It starts by finding a minimal
$\gamma$-alternating path including the new edge in the stream, if
one such exists; this path is denoted by $Q$. The algorithm then may
include two alternating sub-paths of $Q$ and flip the shadow edges
to matching edges, and vice versa in them. Consider one of such
paths, denoted by $Q_1=\{a_r, b_r, a_{r+1}, b_{r+1}, \ldots, a_k,
b_k\}$ (this notation is consistent with that in
Algorithm~\ref{alg:shadow_algorithm} unless we are in the case where
$Q_1=Q$. Even in the latter case, the rest of this proof goes
through identically.) Here, each $(a_i, b_i)$ is a matching edge at
time $t$ but not at time $t+1$; each $b_i, a_{i+1}$ is a shadow edge
at time $t$ and gets included in the matching at time $t+1$. We
first establish three properties about this path, using the
algorithm ($w(x,y)$ is used to denote the weight of an edge $(x,y)$)
:
%\begin{itemize}
%\item

%1. For all $i\geq r$, $\sum_{j=i}^{k}{w(a_jb_j)}\leq
%\frac{1}{\gamma}\cdot \sum_{j=i}^{k}{w(b_j,a_{j+1})}$.
%%\item


1. For every  $j\geq r$, $\sum_{i=j}^{k-1}{w(b_ia_{i+1})}\geq
\gamma\cdot\sum_{i=j+1}^{k}{w(a_ib_i)}$.

%2. $\sum_{j=1}^{k}{w(a_j, b_j)}\leq \frac{1}{\gamma}\cdot
%\sum_{j=1}^{k-1}{w(b_j, a_{j+1})}$.
%\item

2. $\sum_{i=r}^{k-1}{w(b_ia_{i+1})}\geq
\gamma\cdot\sum_{i=r}^{k}{w(a_ib_i)}$

3. For all $j>r$, $\sum_{i=j}^{k-1}{w(b_ia_{i+1})} <
\gamma\cdot\sum_{i=j}^{k}{w(a_ib_i)}$.
%\end{itemize}


The first property follows from the minimality of $Q$. The second
property is due to the fact that $Q_1$ is a $\gamma$-alternating
path. Finally, the third property is because $Q_1$ is a
\textit{minimal} $\gamma$-alternating path.

%These properties follow from the algorithm; notice that to start
%with, the {\em minimal} path picked to contain the new edge $e$.
%Thereafter, the algorithm starts with the two extreme edges on this
%path, and collects edges to form two alternative paths as long as
%the wet of shadow edges does not exceed $\gamma$ times the weight of
%matching edges (that will get deleting when these shadow edges enter
%the matching). Consider either of these paths, where the algorithm
%begins from $u_1$. Notice that by construction, the second property
%is satisfied. Further, the first property is satisfied because if
%there was some $l$ such that $\sum_{j=1}^{l}{w(u_j,v_j)} >
%\frac{1}{\gamma}\cdot \sum_{j=1}^{l}{w(v_j,u_{j+1})}$, then the
%minimal alternating path wouldn't have included these edges.
%Finally, the third property is satisfied as if there is an $l\leq
%k-1$ such that $\sum_{j=1}^{l}{w(u_j,v_j)}< \frac{1}{\gamma}\cdot
%\sum_{j=1}^{l-1}{w(v_j,u_{j+1})}$, then the algorithm, when starting
%from $u_1$, would have stopped at $v_i$ to find its path.

We now show that with these properties, every edge in $Q_1$
satisfies the property in the Lemma. For all $r\leq i \leq k$, we
now define $f_t(a_i)$ and $f_t(b_i)$ explicitly and prove the claim
inductively. The induction is on the length of the path.

% any alternating path $u_1,
%v_1, u_2, v_2, \ldots, u_k, v_k$ picked for being flipped by our
%algorithm satisfies
%the property in the lemma. Assume without loss of generality that
%$k$ is odd, therefore, the path starts and ends with edges that are
%in the matching at time $t$ and alternate between shadow edges. We
%now define $f_t(u)$ explicitly for every vertex $u$ and prove the
%claim inductively. The induction is on the length of the path.

We now set $f(b_k)=0$ and $f(a_k)=1$. To satisfy $f(a_k)w(a_kb_k) +
f(b_{k-1})w(b_{k-1}a_{k-1})\leq \frac{1}{\gamma}\cdot
w(a_kb_{k-1})$, we split $(b_{k-1}a_{k-1})$ into two edges
$b_{k-1}a_{k-1, 1}$ and $a_{k-1, 2},b_{k-1}$ such that
$w(b_{k-1}a_{k-1, 1}) + w(a_{k-1, 2}b_{k-1}) = w(a_{k-1}b_{k-1})$.
Now, consider the requirement on $a_kb_k, a_{k}b_{k-1},
b_{k-1}a_{k-1, 1}$. We now need $f(b_{k-1})\geq 0$ and if
$\frac{w(b_{k-1}a_{k-1})}{\gamma}\geq w(a_kb_{k-1})$, then one can
satisfy the requirement while ensuring that $w(a_{k-1, 2}b_{k-1})$
is positive. Induction then completes to proof. To check
$\frac{w(b_{k-1}a_{k-1})}{\gamma}\geq w(a_kb_{k-1})$, this follows
from the first property. Further, due to the second and third
properties, on inducting on $a_{k-1, 2}b_{k-1}, \ldots, b_1, a_1$,
the property continues to hold.
%\qed
\end{proof}


Now it only remains to describe the charging scheme that maintains
the Invariant~\ref{inv:main} and achieves
Lemma~\ref{lem:finish_charging_scheme}. This charging scheme
considers all types of edges, case by case. To simplify the
analysis, we prove some assumptions that can be made on the input
graph in Section~\ref{sec:simplify_input_graph}. We then show the
general charging scheme in Section~\ref{sec:charging_scheme} and
prove the correctness of Invariant~\ref{inv:main} and
Lemma~\ref{lem:finish_charging_scheme} in Section~\ref{sec:proofs}.
